public class Test2 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //用子问题思路
        //两个树相同==根节点相同+左子树相同+右子树相同

        //这种情况:两个树都为空，那肯定就一样（或者两个左子树，两个右子树都为空，也代表左子树和右子树一样的
        if(p==null&&q==null){
            return true;
        }
        //这两种情况，已经结构不一样了，也不用去关心值一样不一样
        if(p==null&&q!=null) return false;
        if(q==null&&p!=null) return false;
        boolean left=isSameTree(p.left,q.left);
        boolean right=isSameTree(p.right,q.right);
        //这种情况，两个都不为空，要是两个树的值/左子树的值/右子树的值一样，那么就可以判断结构一样了

//这一句才是真正的判断，其他的都是为了找到不符合的，然后他跳出
        if(p.val==q.val&&left==true&&right==true){
            return true;
        }
        return false;
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //用子问题的方法
        //判断一个树是不是另一棵树的子树
        //判断一个树是不是另一个树的左子树/右子树
        if(root==null&&subRoot==null) return true;
        //这种情况应该不太可能，太离谱了
        if(root==null&&subRoot!=null) return false;
        if(root!=null&&subRoot==null) return true;
        if(isSameTree(root,subRoot)==true){
            return true;
        }
        if(root.left!=null){
            return isSubtree(root.left,subRoot);
        }
        if(root.right!=null){
            return isSubtree(root.right,subRoot);
        }
        return false;
    }



}
class test{
    public static void main(String[] args) {
        Test2 test2=new Test2();
        //
    }
}

